package com.atguigu.sort;

public class RadixSort {
    public static void radixSort(int[] a,int L,int R,int digit){
        final int radix=10;
        int i=0,j=0;
        //有多少个数准备多少个辅助空间
        int[] bucket=new int[R-L+1];
        for(int d=1;d<=digit;d++){ //有多少位就进出几次
            //10个空间
//            count[0] 当前位上是0的数字有几个
//                count[1] 当前位上是0和1的数字有几个
//                count[2] 当前位上是0，1,2的数字有几个
            int[] count=new int[radix]; //
            for(i=L;i<=R;i++){
               // j=getDigit(a[i],d); //获取该位上的数
                count[j]++;
            }
            //前缀和
            for(i=1;i<radix;i++){
                count[i]=count[i]+count[i-1];
            }
            //倒序进行出桶
            for(i=R;i>=L;i--){
            //    j=getDigit(a[i],d);
                bucket[count[j]-1]=a[i];
                count[j]--;
            }
            for(i=L,j=0;i<=R;i++,j++){
                a[i]=bucket[j];
            }
        }
    }
}
